/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution
{
public:
    Node *copyRandomList(Node *head)
    {
        if (head == nullptr)
        {
            return nullptr;
        }
        unordered_map<Node *, Node *> nodeMap;
        Node *copiedHead = new Node(head->val);
        nodeMap[nullptr] = nullptr;
        nodeMap[head] = copiedHead;
        Node *cur = head;
        Node *copiedCur = copiedHead;
        while (cur->next != nullptr)
        {
            copiedCur->next = new Node(cur->next->val);
            cur = cur->next;
            copiedCur = copiedCur->next;
            nodeMap[cur] = copiedCur;
        }
        cur = head;
        copiedCur = copiedHead;
        while (cur != nullptr)
        {
            copiedCur->random = nodeMap[cur->random];
            cur = cur->next;
            copiedCur = copiedCur->next;
        }
        return copiedHead;
    }
};